We consider linear-programming (LP) decoding of low-density parity-check(LDPC) codes. While it is clear that one can use any general-purpose LP solverto solve the LP that appears in the decoding problem, we argue in this paperthat the LP at hand is equipped with a lot of structure that one should takeadvantage of. Towards this goal, we study the dual LP and show howcoordinate-ascent methods lead to very simple update rules that are tightlyconnected to the min-sum algorithm. Moreover, replacing minima in the formulaof the dual LP with soft-minima one obtains update rules that are tightlyconnected to the sum-product algorithm. This shows that LP solvers withcomplexity similar to the min-sum algorithm and the sum-product algorithm arefeasible. Finally, we also discuss some sub-gradient-based methods.
展开▼
